# LeetCode 51、N 皇后

# 一、题目描述

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q''.' 分别代表了皇后和空位。

输入:n = 4
输出:[[".Q..","...Q","Q...","..Q."],
["..Q.","Q...","...Q",".Q.."]]
解释:4 皇后问题存在两个不同的解法。

# 二、题目解析

# 三、参考代码

# 1、Java 代码

class Solution {

    // 保存所有符合要求的解
    List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
      
      // attack 用来表示皇后的攻击范围
      int[][] attack = new int[n][n];
      // queen 用来记录皇后的位置
      char[][] queen = new char[n][n];

      // 初始化二维数组 queen 中所有的元素为 '.'
      for(char[] c : queen) {
         Arrays.fill(c, '.');
      }

      // 初始化二维数组 attack 中所有的元素为 0
      // 0 代表没有皇后能攻击得到
      // 1 代表出于任意一个皇后的攻击范围内
      for(int[] c : attack) {
          Arrays.fill(c, 0);
      }

      // 从棋盘的第 0 行第 0 列处理 n 皇后的情况
      backtrack(0,n,queen,attack);

      // 最后,返回所有符合要求的解
      return res;
    }

    // 很显然,每一行只能放置一个皇后,所以我们每一行每一行的来放置皇后
    // k 表示当前处理的行
    // n 表示需要放置多少个皇后,同时也代表棋盘的大小为 n * n
    // queen 用来记录皇后的位置
    // attack 用来表示皇后的攻击范围
    private void backtrack(int k ,int n , char[][] queen,int[][] attack){

        // 如果发现在棋盘的最后一行放置好了皇后,那么就说明找到了一组符合要求的解
        if(k == n){
            // 由于 queen 为二维字符数组,所以需要转换为字符串数组
            List<String> list = new ArrayList<>();
            // 遍历二维数组 queen
            // 取出 queen 的每一行字符数组 c
            for (char[] c : queen) {
                // 把字符数组 c 中的所有字符转换为字符串的形式进行拼凑
                // 比如 ['.','Q','.','.',]
                // 转换为 '.Q..'
                // 把这个字符串加入到 list 中
                list.add(String.copyValueOf(c));
            }

            // list 即为一组符合要求的解,把它加入到结果数组中
            res.add(list);
            // 由于遍历完了所有的行,无需再遍历下去,所以返回
            return;
        }

        // 每一行只能放置一个皇后
        // 并且每一列也只能放置一个皇后
        // 所以在 k 行中,从 0 列到 n - 1 列,判断皇后应该放置到哪个位置
        for(int i = 0 ; i < n ; i++){
            // 如果发现 attack[k][i] == 0
            // 说明这个位置不在任何一个皇后的攻击范围内
            // 所以可以考虑放置皇后
            if(attack[k][i] == 0){

                // 如果在 ( k , i ) 位置放置了皇后,那么就需要考虑在 k + 1 行应该怎么放置其它的皇后了
                // 由于有可能在( k , i )  位置放置了皇后之后,在后续的其它行会无法再放置其它的皇后
                // 那么就需要回到 ( k , i )  的状态,考虑能不能在 ( k , i + 1 )的位置放置
                // 为了能够回到 ( k , i )  的状态,所以需要先记录此时的 attack
                // 使用一个临时的二维数组,深度拷贝 attack
                // 如果不使用深度拷贝,而是直接使用 int[][] temp = c
                // 会导致 attack 发生改变是 temp 也会发生改变
                // 这样也就无法保存之前的状态了
                int[][] temp = new int[n][n];
                
                // 通过两个 for 循环,把 attack 中的所有元素深度拷贝到 temp
                for(int l = 0 ; l < n ; l++){
                    for( int m = 0 ; m < n ; m++){
                        temp[l][m] = attack[l][m];
                    }
                }

                // queen 用来记录皇后的位置
                // 那么 ( k , i )  的位置 queen[k][i] = 'Q'
                queen[k][i] = 'Q';

                // 由于新放置了一个皇后,所以攻击范围又更多了
                // 所以需要更新 attack 数组
                // 新放置皇后的坐标为 ( k , i ) ,同样的需要更新它的八个方向
                checkQueenAttack(k,i,attack);
                
                // 如果在 ( k , i )  位置放置了皇后,那么就需要考虑在 k + 1 行应该怎么放置其它的皇后
                // 递归的调用 backtrack 在 k + 1 行放置皇后
                backtrack(k + 1,n,queen,attack);
                
                // 递归结束后,拿走皇后,恢复 attack 的状态,考虑能不能在 ( k ,i + 1 )的位置放置
                attack = temp;

                // 恢复 queen 的状态,说明此时皇后不放置在( k , i )  位置
                queen[k][i] = '.';
            }
        }


    }

    // 坐标 ( x , y) 为皇后所处的位置
    // 更新 attack
    private void checkQueenAttack(int x ,int y,int[][] attack){

        // 对于每一个坐标 (x,y) 来说,都有上、下、左、右、左上、左下、右上、右下 八个方向
        //【左上】的坐标为 (x - 1, y - 1)
        //【上】的坐标为 (x - 1, y )
        //【右上】的坐标为 (x - 1, y + 1)
        //【左】的坐标为 (x, y + 1)
        //【右】的坐标为 (x , y - 1)
        //【左下】的坐标为 (x + 1, y - 1)
        //【下】的坐标为 (x + 1, y)
        //【右下】的坐标为 (x + 1, y + 1)
        // 通过两个一维数组可以表示这八个方向
        // dx 表示 x 的方向
        int dx[] = { -1 , -1 , -1 , 0  ,  0 ,  1  , 1 , 1 };
        // dy 表示 y 的方向
        int dy[] = { -1 , 0  , 1 , -1 ,  1 ,  -1 , 0 , 1 };

        // 皇后所处的坐标肯定是皇后能攻击的位置,设置为 1
        attack[x][y] = 1;

        // 以坐标 ( x , y) 为中心,去更新它八个方向的坐标
        for(int j = 0 ; j < 8; j++){
            // 由内向外的进行更新
            for(int i = 1 ; i < attack.length ; i++){
                // 新的位置的坐标行为 x + i * dx[j]
                int nx = x + i * dx[j];
                // 新的位置的坐标列为 y + i * dy[j]
                int ny = y + i * dy[j];

                // 如果新位置的坐标在 n * n 的棋盘范围内
                if(nx >= 0 && nx < attack.length && ny >= 0 && ny < attack.length){
                    // 那么这些位置就是在坐标为 (x,y)的皇后的攻击范围内,更新为 1
                    attack[nx][ny] = 1;
                }

            }
        }
    }
}

# **2、**C++ 代码

class Solution {
       // 保存所有符合要求的解
       vector<vector<string>> res;
public:
    vector<vector<string>> solveNQueens(int n) {

      
      // attack 用来表示皇后的攻击范围
      vector<vector<int>> attack(n,vector<int>(n));

      for( int i = 0 ; i < n ; i++){
          for(int j = 0 ; j < n ; j++){
              attack[i][j] = 0;
          }
      }

      // queen 用来记录皇后的位置
      vector<vector<string>> queen(n,vector<string>(n));

      for( int i = 0 ; i < n ; i++){
          for(int j = 0 ; j < n ; j++){
              queen[i][j] = ".";
          }
      }

      // 从棋盘的第 0 行第 0 列处理 n 皇后的情况
      backtrack(0,n,queen,attack);

      // 最后,返回所有符合要求的解
      return res;
    }

    // 很显然,每一行只能放置一个皇后,所以我们每一行每一行的来放置皇后
    // k 表示当前处理的行
    // n 表示需要放置多少个皇后,同时也代表棋盘的大小为 n * n
    // queen 用来记录皇后的位置
    // attack 用来表示皇后的攻击范围
    void backtrack(int k, int n , vector<vector<string>> &queen,vector<vector<int>> &attack){

        // 如果发现在棋盘的最后一行放置好了皇后,那么就说明找到了一组符合要求的解
        if(k == n){

            vector<string> ans = {};

            for(int i = 0 ; i < n ; i++){

                string temp = "";

                for( int j = 0 ; j < n ; j++){

                    temp += queen[i][j];

                }

                ans.push_back(temp);
            }

           
            res.push_back(ans);

            // 由于遍历完了所有的行,无需再遍历下去,所以返回
            return;
        }

        // 每一行只能放置一个皇后
        // 并且每一列也只能放置一个皇后
        // 所以在 k 行中,从 0 列到 n - 1 列,判断皇后应该放置到哪个位置
        for(int i = 0 ; i < n ; i++){
            // 如果发现 attack[k][i] == 0
            // 说明这个位置不在任何一个皇后的攻击范围内
            // 所以可以考虑放置皇后
            if(attack[k][i] == 0){

                // 如果在 ( k , i ) 位置放置了皇后,那么就需要考虑在 k + 1 行应该怎么放置其它的皇后了
                // 由于有可能在( k , i )  位置放置了皇后之后,在后续的其它行会无法再放置其它的皇后
                // 那么就需要回到 ( k , i )  的状态,考虑能不能在 ( k , i + 1 )的位置放置
                // 为了能够回到 ( k , i )  的状态,所以需要先记录此时的 attack
                // 使用一个临时的二维数组,深度拷贝 attack
                // 如果不使用深度拷贝,而是直接使用 int[][] temp = c
                // 会导致 attack 发生改变是 temp 也会发生改变
                // 这样也就无法保存之前的状态了
                vector<vector<int>> temp(n,vector<int>(n));

                
                // 通过两个 for 循环,把 attack 中的所有元素深度拷贝到 temp
                for(int l = 0 ; l < n ; l++){
                    for( int m = 0 ; m < n ; m++){
                        temp[l][m] = attack[l][m];
                    }
                }

                // queen 用来记录皇后的位置
                // 那么 ( k , i )  的位置 queen[k][i] = 'Q'
                queen[k][i] = 'Q';

                // 由于新放置了一个皇后,所以攻击范围又更多了
                // 所以需要更新 attack 数组
                // 新放置皇后的坐标为 ( k , i ) ,同样的需要更新它的八个方向
                checkQueenAttack(k,i,attack);
                
                // 如果在 ( k , i )  位置放置了皇后,那么就需要考虑在 k + 1 行应该怎么放置其它的皇后
                // 递归的调用 backtrack 在 k + 1 行放置皇后
                backtrack(k + 1,n,queen,attack);
                
                // 递归结束后,拿走皇后,恢复 attack 的状态,考虑能不能在 ( k ,i + 1 )的位置放置
                attack = temp;

                // 恢复 queen 的状态,说明此时皇后不放置在( k , i )  位置
                queen[k][i] = '.';
            }
        }


    }

    // 坐标 ( x , y) 为皇后所处的位置
    // 更新 attack
    void checkQueenAttack(int x ,int y, vector<vector<int>> &attack){

        // 对于每一个坐标 (x,y) 来说,都有上、下、左、右、左上、左下、右上、右下 八个方向
        //【左上】的坐标为 (x - 1, y - 1)
        //【上】的坐标为 (x - 1, y )
        //【右上】的坐标为 (x - 1, y + 1)
        //【左】的坐标为 (x, y + 1)
        //【右】的坐标为 (x , y - 1)
        //【左下】的坐标为 (x + 1, y - 1)
        //【下】的坐标为 (x + 1, y)
        //【右下】的坐标为 (x + 1, y + 1)
        // 通过两个一维数组可以表示这八个方向
        // dx 表示 x 的方向
        int dx[8] = { -1 , -1 , -1 , 0  ,  0 ,  1  , 1 , 1 };
        // dy 表示 y 的方向
        int dy[8] = { -1 , 0  , 1 , -1 ,  1 ,  -1 , 0 , 1 };

        // 皇后所处的坐标肯定是皇后能攻击的位置,设置为 1
        attack[x][y] = 1;

        // 以坐标 ( x , y) 为中心,去更新它八个方向的坐标
        for(int j = 0 ; j < 8; j++){
            // 由内向外的进行更新
            for(int i = 1 ; i < attack.size() ; i++){
                // 新的位置的坐标行为 x + i * dx[j]
                int nx = x + i * dx[j];
                // 新的位置的坐标列为 y + i * dy[j]
                int ny = y + i * dy[j];

                // 如果新位置的坐标在 n * n 的棋盘范围内
                if(nx >= 0 && nx < attack.size() && ny >= 0 && ny < attack.size()){
                    // 那么这些位置就是在坐标为 (x,y)的皇后的攻击范围内,更新为 1
                    attack[nx][ny] = 1;
                }

            }
        }
    }
};

# 3、Python 代码

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        # 更新皇后的坐标[x][y]之后更新attack的位置
        def updateAttack(x,y,attack):
            # 更改attack[x][y]上、下、左、右、左上、左下、右上、右下的0为1
            # dx表示x的方向,dy表示y的方向
            dx = [-1, -1, 1, 0, 0, 1, 1, 1]
            dy = [-1, 0, 1, -1, 1, -1, 0, 1]
            # 八个方向更新
            for j in range(8):
                # 内到外更新
                for i in range(n):
                    nx = x + i * dx[j]
                    ny = y + i * dy[j]
                    # 新坐标在棋盘内则更新
                    if nx >= 0 and nx < n and ny >= 0 and ny < n:
                        attack[nx][ny] = 1

        # k为当前处理的行
        # n表示需要放置的皇后数和棋盘大小
        # queen皇后的位置
        # attack攻击范围
        def backtrack(k,n,queen,attack):
            print(k)
            # 如果棋盘最后一行放置好了皇后则找到一组解
            if k == n:
                rl = []
                # queen为分隔的二维数组,去转为字符串数组
                for i in queen:
                    rl.append(''.join(i))
                res.append(rl)
                return
            
            # 每行每列只能放一个皇后,所以在k行中,从0~n-1列判断皇后放置的位置
            for i in range(n):
   
                # 如果attack[k][i]为0,即不在攻击范围内,可考虑放置皇后
                if attack[k][i] == 0:
                    # k行i列放置后需考虑k+1行如何放置
                    # 若k+1无法放置,需回退,考虑k行i+1列能否放置
                    # 用临时数组记录k行i列时的attack状态
                    # temp = attack[:]
                    # 要使用深度拷贝
                    temp =  copy.deepcopy(attack)

                    queen[k][i] = 'Q'
                    # 更新attack数组
                    updateAttack(k,i,attack)
                    # print(attack,queen,'after')
                    # 递归的调用backtrack考虑在k+1行放置皇后
                    backtrack(k+1,n,queen,attack)

                    # 递归结束移走皇后恢复[k][i]不能放置状态
                    attack = temp
                    # print(attack,3)
                    # 恢复queen状态
                    queen[k][i] = '.'
        
        res = []
        # attack表示皇后攻击范围
        # 初始化攻击为0 
        '''0表示没有皇后能攻击得到,1表示处于任意一个皇后的攻击范围内'''
        attack = []
        for i in range(n):
            attack.append([0] * n)
        # queen记录皇后位置
        # 初始化queen所有元素为'.'
        queen = []
        for i in range(n):
            queen.append(['.'] * n)
        # 从棋盘的第0行第0列处理n皇后情况
        backtrack(0, n, queen, attack)
        # 返回结果
        return res